/**
* @description: 877. 石子游戏
* @author hewei
* @date 2022/9/13 17:01
* @version 1.0
*/

public class StoneGame {

    public boolean stoneGame1(int[] piles) {
        int sum = 0;
        for (int i = 0; i < piles.length; i++) {
            sum += piles[i];
        }
        return f(piles, 0, piles.length - 1) > sum / 2;
    }

    public int f(int[] piles, int l , int r) {
        if (l == r) return piles[l];
        return Math.max(piles[l] + s(piles, l + 1, r), piles[r] + s(piles, l, r - 1));
    }

    public int s(int[] piles, int l, int r) {
        if (l == r) return 0;
        return Math.min(f(piles, l + 1, r), f(piles, l, r - 1));
    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        // 先手拿到的分数 - 后手拿到的分数
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[i][j] = piles[i];
                } else {
                    dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1] > 0;
    }
}
